package cn.lucky.datastructure;

import java.util.Stack;

/**
 * @author lingpeng.jiang
 * @create 2021-01-31-20:28
 * 表达式解析
 */
public class Expression {

    /**
     * 中缀表达式转换为后缀表达式
     * @param infix 中缀表达式
     */
    private static void infixChangeSuffix(String infix){
        //运算符栈
        Stack<Character> operator = new Stack<Character>();
        //操作数栈
        Stack<Object> operand = new Stack<Object>();

        char c;
        int nonOperandIndex = -1;
        int len = infix.length();
        String tempOperand;
        for (int i = 0; i < len; i++) {//(36.22+4.32)*2.35+5.98
            c = infix.charAt(i);
            //判断c是否为数字
            if (Character.isDigit(c)){
                nonOperandIndex = getNonOperandIndexBefore(infix,i);
                tempOperand = infix.substring(i,nonOperandIndex);
                operand.push(tempOperand);
                i = nonOperandIndex - 1;
                //System.out.println(tempOperand + "   ");
                continue;
            }
            if (isOperator(c)) {
                while (!(operator.isEmpty() || c == '(' || !priorityCompare(c,operator.peek()))){
                    operand.push(operator.pop());
                }
                operator.push(c);
                continue;
            }
            if (c == ')'){
                while (operator.peek() != '('){
                    operand.push(operator.pop());
                }
                if (!operator.isEmpty()){
                    operator.pop();//丢掉（括号
                }
                continue;
            }
            operator.push(c);
            //displayStackOperator(operator);
        }
        //将运算符栈中剩余的元素压入到操作数栈中
        while (!operator.isEmpty()){
            operand.push(operator.pop());
        }
        displayStack(operand);


    }



    private static void displayStack(Stack<Object> operand){
        Stack<Object> reversal = new Stack<Object>();
        while (!operand.isEmpty()){
            reversal.push(operand.pop());
        }
        while (!reversal.isEmpty()){
            System.out.print(reversal.pop() + " ");
        }
    }


    /**
     * 比较两个运算符的优先级别
     * @param originChar
     * @param stackPeek
     * @return
     */
    private static boolean priorityCompare(char originChar, char stackPeek){
        if (originChar == '+' || originChar == '-'){
            return stackPeek != '*' && stackPeek != '/';
        }
        if (stackPeek == '+' || stackPeek == '-'){
            return originChar != '*' && originChar != '/';
        }
        return true;
    }

    /**
     * 判断字符是否为+-*\/
     * @param c
     * @return
     */
    private static boolean isOperator(char c){
        return c == '+' || c == '-' || c == '*' || c == '/';
    }



    /**
     * 查找当前操作数后面的运算符
     * @param infix 中缀表达式
     * @param startIndex 开始索引
     * @return
     */
    private static int getNonOperandIndexBefore(String infix,int startIndex){
        char c;
        int rsIndex = -1;
        int len = infix.length();
        for (int i = startIndex; i < len; i++) {
            c = infix.charAt(i);
            if (c == '.'){
            } else if (!Character.isDigit(c)){
                rsIndex = i;
                break;
            } else if (i == len - 1){
                rsIndex = len;
            }
        }
        return rsIndex;
    }




    public static void main(String[] args) {
        System.out.println("34.6+56.2+58*63-69");
        Expression.infixChangeSuffix("34.6+56.2+58*63-69");
    }
}
